﻿using System.Collections.Generic;
using System.Numerics;

namespace psieve.factor
{
    public class TrialDivision : IFactor
    {
        private readonly ISieve sieve;

        public TrialDivision(ISieve sieve)
        {
            this.sieve = sieve;
        }

        private BigInteger CollectFactors(BigInteger num, IEnumerable<long> primes, List<BigInteger> factors)
        {
            foreach (long p in primes)
            {
                if (p * p > num)
                    break;
                while (num % p == 0)
                {
                    factors.Add(p);
                    num /= p;
                }
            }

            return num;
        }

        public IEnumerable<BigInteger> Factor(BigInteger num)
        {
            if(num == 1)
                return new List<BigInteger>(1);

            List<BigInteger> factors = new List<BigInteger>();

            // try small primes first
            num = CollectFactors(num, sieve.Sieve(10000), factors);

            int sqrt = (int) num.Sqrt();

            if (num > 1)
                num = CollectFactors(num, sieve.Sieve(sqrt + 1), factors);

            if(num > 1)
                factors.Add(num);           

            return factors;
        }
    }
}
